class Solution:
    def kSmallestPairs(self, nums1: list, nums2: list, k: int) -> list:
        """这个不对"""
        i, j = 0, 0
        res = []
        k = min(k, len(nums1) * len(nums2))
        nums1.append(float("inf"))
        nums2.append(float("inf"))
        while len(res) < k:
            res.append([nums1[i], nums2[j]])
            if nums1[i + 1] > nums2[j + 1]:
                j += 1
            elif nums1[i + 1] < nums2[j + 1]:
                i += 1
            else:
                if nums1[i] > nums2[j]:
                    j += 1
                elif nums1[i] < nums2[j]:
                    i += 1
                else:
                    if len(res) == k:
                        break
                    res.append([nums1[i + 1], nums2[j]])
                    if len(res) == k:
                        break
                    res.append([nums1[i], nums2[j + 1]])
                    i += 1
                    j += 1
        return res


from collections import deque


class Solution2:
    def kSmallestPairs(self, nums1: list, nums2: list, k: int) -> list:
        len1, len2 = len(nums1), len(nums2)
        res = []
        k = min(k, len1 * len2)
        if len1 and len2:
            sum_list = deque([nums1[i] + nums2[0], i, 0] for i in range(len1))
            sum_list.append([float("inf"), float("inf"), float("inf")])
            while k:
                sum_num, i, j = sum_list.popleft()
                res.append([nums1[i], nums2[j]])
                if j + 1 < len2:
                    mid_num, l = nums1[i] + nums2[j + 1], 0
                    while mid_num > sum_list[l][0]:
                        l += 1
                    sum_list.insert(l, [mid_num, i, j + 1])
                k -= 1
        return res


a = Solution2()
print(a.kSmallestPairs(nums1=[1, 7, 11], nums2=[2, 4, 6], k=4))
print(a.kSmallestPairs(nums1=[1, 1, 2], nums2=[1, 2, 3], k=2))
print(a.kSmallestPairs(nums1=[1, 1, 2], nums2=[1, 2, 3], k=0))
print(a.kSmallestPairs(nums1=[1, 2], nums2=[3], k=3))
print(a.kSmallestPairs([1, 1, 2], [1, 2, 3], 10))
